package one;

public class A007 {


    /**
     * 解法一：dp优化掉数组，使用两个双指针代替
     * @param height
     * @return
     */
    public int trap(int[] height) {
        //
        int n = height.length;
        int dp_left = 0;//i位置左边最高的柱子
        int dp_right = 0;

        int ret = 0;//
        int left=1,right=n-2;
        for(int i=1;i<n-1;i++) {
            if(height[left-1] < height[right+1]) {
                //左边高度 < 右边高度
                dp_left = Math.max(dp_left,height[left-1]);
                int min = dp_left;
                if(min > height[left]) {
                    ret += min - height[left];
                }
                left++;
            }else {
                //左边高度 > 右边高度
                dp_right = Math.max(dp_right,height[right+1]);
                int min = dp_right;
                if(min > height[right]) {
                    ret += min - height[right];
                }
                right--;
            }
        }
        return ret;
    }


    /**
     * 解法一：动态规划+一列一列求雨水
     * @param height
     * @return
     */
    public int trap1(int[] height) {
        //
        int n = height.length;
        int[] dp_left = new int[n];//i位置左边最高的柱子
        int[] dp_right = new int[n];
        for(int i=1;i<n-1;i++) {
            dp_left[i] = Math.max(dp_left[i-1],height[i-1]);
        }
        for(int i=n-2;i>0;i--) {
            dp_right[i] = Math.max(dp_right[i+1],height[i+1]);
        }
        int ret = 0;//
        for(int i=1;i<n-1;i++) {
            if(Math.min(dp_left[i],dp_right[i]) > height[i]) {
                ret += Math.min(dp_left[i],dp_right[i]) - height[i];
            }
        }
        return ret;
    }
}
